home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / priority_queue.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  3.2 KB  |  90 lines
  1. {\magonebf 4.1 Priority Queues (priority\_queue)}
  2.  
  3. \decltwo priority\_queue K I 
  4.  
  5. {\bf 1. Definition}
  6.  
  7. An instance $Q$ of the parameterized data type \name\ is a
  8. collection of items (type $pq\_item$). Every item contains a key from type 
  9. $K$ and an information from the linearly ordered type $I$. $K$ is called the 
  10. key type of $Q$ and $I$ is called the information type of $Q$. The number of 
  11. items in $Q$ is called the size of $Q$. If $Q$ has size zero it is called the 
  12. empty priority queue. We use $<k,i>$ to denote a $pq\_item$\ with key $k$ and 
  13. information $i$.
  14.  
  15. \bigskip
  16. {\bf 2. Creation}
  17.  
  18. a) \create Q {}
  19.  
  20. b) $\_priority\_queue${\tt <}$K,I,prio\_impl${\tt >} $Q$;
  21.  
  22. creates an instance \var\ of type \name\ and initializes it with the
  23. empty priority queue. Variant a) chooses the default data structure
  24. (cf.~4.1.4), and variant b) chooses class $prio\_impl$ as the 
  25. implementation of the queue (cf.~section~9 for a list of possible
  26. implementation parameters).
  27.  
  28.  
  29. \bigskip
  30. {\bf 3. Operations }
  31.  
  32. \+\cleartabs & \hskip 1.8truecm & \hskip 6truecm &\cr
  33. \+\op K        key {pq\_item\ it}    
  34.                            {returns the key of item $it$.}
  35. \+\nop                     {\precond $it$ is an item in \var.}
  36. \smallskip
  37. \+\op I        inf {pq\_item\ it}    
  38.                            {returns the information of item $it$.}
  39. \+\nop                     {\precond $it$ is an item in \var.}
  40. \smallskip
  41. \+\op pq\_item insert {K\ k,I\ i} 
  42.                            {adds a new item $<k,i>$ to \var\ and returns $it$.}
  43. \smallskip
  44. \+\op pq\_item find\_min {}       
  45.                            {returns an item with minimal information}
  46. \+\nop                     {(nil if \var\ is empty)}
  47. \smallskip
  48. \+\op void     del\_item {pq\_item\ it} 
  49.                            {removes the item $it$ from \var.}
  50. \+\nop                     {\precond $it$ is an item in \var.}
  51. \smallskip
  52. \+\op K        del\_min {} 
  53.                            {removes the item $it$ = \var.find\_min() from \var}
  54. \+\nop                     {and returns the key of $it$.}
  55. \+\nop                     {\precond \var\ is not empty.}
  56. \smallskip
  57. \+\op void     decrease\_inf {pq\_item\ it,\ I\ i} 
  58.                            {makes i the new information of item $it$}
  59. \+\nop                     {\precond $it$ is an item in \var\ and $i$}
  60. \+\nop                     {is not larger then $inf(it)$.}
  61. \smallskip
  62. \+\op void     change\_key {pq\_item\ it,\ K\ k} 
  63.                            {makes k the new key of item $it$}
  64. \+\nop                     {\precond $it$ is an item in \var.}
  65. \smallskip
  66. \+\op void     clear {}        
  67.                            {makes \var\ the empty priority queue }
  68. \smallskip
  69. \+\op bool     empty {} 
  70.                            {returns true, if \var\ is empty, false otherwise}
  71. \smallskip
  72. \+\op int      size  {}
  73.                            {returns the size of \var.}
  74.  
  75.  
  76. \bigskip
  77. {\bf 4. Implementation}
  78.  
  79. Priority queues are implemented by Fibonacci heaps ([FT84]. Operations insert, 
  80. del\_item, del\_min take time $O(\log n)$, find\_min, decrease\_inf, 
  81. key, inf, empty take time $O(1)$ and clear takes time $O(n)$, where $n$ is the 
  82. size of \var. The space requirement is $O(n)$.
  83.  
  84.  
  85. \bigskip
  86. {\bf 5. Example}
  87.  
  88. Dijkstra's Algorithm (cf.~section 8.1)
  89.  
  90.